package greed

import "math"

func maxProfit(prices []int) int {
	if prices == nil || len(prices) == 0 {
		return 0
	}
	n := len(prices)
	dp := make([][2]int, n)
	// dp[i][0] 代表第i天结束时，持有股票的最大利润
	// dp[i][1] 代表第i天结束时，不持有股票的最大利润
	dp[0][0] = -prices[0]
	dp[0][1] = 0
	for i := 1; i < n; i++ {
		dp[i][0] = max(-prices[i], dp[i-1][0])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
	}
	return dp[n-1][1]
}

func maxProfit2(prices []int) int {
	minP := math.MaxInt32
	maxPf := 0
	for i := 0; i < len(prices); i++ {
		if prices[i] < minP {
			minP = prices[i]
		} else if prices[i] - minP > maxPf {
			maxPf = prices[i] - minP
		}
	}
	return maxPf
}